Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All : You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste : You can paste the characters which are copied last time .

Given a numbern. You have to getexactlyn'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to getn'A'.

Example 1:

Input:
 3

Output:
 3

Explanation:

Intitally, we have one character 'A'.
In step 1, we use 
Copy All
 operation.
In step 2, we use 
Paste
 operation to get 'AA'.
In step 3, we use 
Paste
 operation to get 'AAA'.

Note:

1. The n will be in the range [1, 1000].

class Solution {

public:

int minSteps\(int n\) {

    int dp\[n+1\];

    dp\[0\]=0;

    if\(n==0\){

        return 0;

    }

    if \(n==1\){

        return 0;

    }

    if \(n>=2\){

        dp\[1\]=0;

        dp\[2\]=2;

    }



    for \(int i=3;i<=n;i++\){

        dp\[i\]=1000000000;

        for\(int j=i-1;j>=1;j--\){

            if\(i%j==0\){

                dp\[i\]=dp\[j\]+i/j;

                break;

            }

        }

    }



    return dp\[n\];

}

};

哇这个很特别。我开始想的是用减法。然后发现6的时候最小的是先到3，然后粘贴一次。但是这样的话，7就没法处理了，因为7不能够拆成6和1的情况处理。1这种情况在处理6的时候已经消失了。

再比如说9，那么可能有种情况是3*3etc。所以这个找最大因子的方法真的很巧妙啊。